import com.sun.org.apache.xerces.internal.xs.LSInputList;
import org.w3c.dom.ls.LSInput;

import java.util.*;

/**
 * @program: leetcode023
 * @author: JCM
 * @create: 2022-11-28 19:25
 * @description: 合并 K 个升序链表
 **/


class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class LeetCode023 {
    public ListNode mergeKLists(ListNode[] lists) {
        // len 记录所有链表的总数据个数
        int len = 0;
        for(int i=0; i < lists.length; i++) {
            ListNode l = lists[i];
            while(l != null) {
                len++;
                l = l.next;
            }
        }
        // 如果数据个数为 0 直接返回空链表
        if(len == 0) {
            return null;
        }
        // 用一个数组将所有数据保存下来
        int[] nums = new int[len];
        int j = 0;
        for(int i=0; i < lists.length; i++) {
            ListNode l = lists[i];
            while(l != null) {
                nums[j] = l.val;
                j++;
                l = l.next;
            }
        }
        // 对数组进行排序
        Arrays.sort(nums);
        // 将数组中的数据依次进行尾插
        ListNode head = new ListNode(nums[0],null);
        ListNode cur = head;
        for(int i=1; i < len; i++) {
            ListNode newNode = new ListNode(nums[i],null);
            cur.next = newNode;
            cur = cur.next;
        }
        return head;
    }

}
